package com.zxy.leetcode._00200_00299._00210_00219;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/combination-sum-iii/
 *
 * 组合总和 III
 *
 * 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，
 * 并且每种组合中不存在重复的数字。
 *
 * 说明：
 * 所有数字都是正整数。
 * 解集不能包含重复的组合。 
 *
 * 标签：组合、回溯算法
 */
public class Test00216 {

    public static void main(String[] args) {
        Test00216 test = new Test00216();
        List<List<Integer>> result = test.combinationSum3(3, 7);
        System.out.println(result);

        result = test.combinationSum3(3, 9);
        System.out.println(result);
    }

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        if (k == 0 || n == 0) {
            return result;
        }

        backtrack(result, new ArrayDeque<>(), k, n);

        return result;
    }

    private void backtrack(List<List<Integer>> result, Deque<Integer> selectDeque, int k, int n) {
        if (selectDeque.size() == k) {
            if (selectDeque.stream().mapToInt(Integer::intValue).sum() == n) {
                result.add(new ArrayList<>(selectDeque));
            }
            return;
        }

        if (selectDeque.size() >= k) {
            return;
        }

        for (int i=1; i<=9; i++) {
            if (!selectDeque.isEmpty()) {
                // 防重复处理
                if (selectDeque.getLast() >= i) {
                    continue;
                }
            }

            selectDeque.add(i);
            backtrack(result, selectDeque, k, n);
            selectDeque.removeLast();
        }
    }

}
